package org.example.myleet.rosalind.lrep;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath() + "example.txt";
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path)));
        String source = br.readLine().trim();
        int k = Integer.parseInt(br.readLine().trim());
        List<String> input = new ArrayList<>();
        String line;
        while (null != (line = br.readLine())) {
            line = line.trim();
            if (line.length() < 1) {
                break;
            }
            input.add(line);
        }
        SuffixTree suffixTree = new SuffixTree(source, input);
        suffixTree.dfsFindLongestSubstringOfLeastK(k, suffixTree.root, new StringBuilder());
        System.out.println(suffixTree.candidate);
        br.close();
    }

    static class SuffixTree {
        SuffixTreeNode root;

        int k;
        int maxLen;
        String candidate;

        public SuffixTree(String source, List<String> input) {
            //根据输入的所有节点的边重构后缀树
            //root是一个dummy节点
            this.root = new SuffixTreeNode("root", "");
            Map<String, SuffixTreeNode> labelMapNode = new HashMap<>(input.size());
            for (String line : input) {
                String[] parts = line.split(" ");
                SuffixTreeNode nodeParent = labelMapNode.get(parts[0]);
                if (null == nodeParent) {
                    nodeParent = new SuffixTreeNode(parts[0], "");
                    labelMapNode.put(parts[0], nodeParent);
                    //没有父节点的nodeParent被挂到root下面
                    this.root.children.add(nodeParent);
                }
                SuffixTreeNode nodeChild = labelMapNode.get(parts[1]);
                if (null == nodeChild) {
                    int start = Integer.parseInt(parts[2]);
                    int len = Integer.parseInt(parts[3]);
                    nodeChild = new SuffixTreeNode(parts[1], source.substring(start - 1, start - 1 + len));
                    labelMapNode.put(parts[1], nodeChild);
                }
                //子节点被挂到父节点下面
                nodeParent.children.add(nodeChild);
            }
        }

        /**
         * 在一个由目标字符串构建出来的后缀树中，要寻找某个字符串S出现了多少次，分成2步：
         * 1、先按字典树的方式搜索找到hold住了S字符串的节点
         * 2、从这个节点开始，找到节点下面所有子节点的叶子节点数目，则叶子节点数目为字符串S在目标字符串中出现的次数
         *
         * 本方法通过DFS的方式寻找某个节点下面的叶子节点的个数，如果叶子节点的个数超过k（最少出现次数），则说明此字符串为候选答案
         */
        public int dfsFindLongestSubstringOfLeastK(int k, SuffixTreeNode cur, StringBuilder sb) {
            if (this.k != k) {
                this.k = k;
                this.maxLen = 0;
                this.candidate = "";
            }
            int delStart = sb.length();
            sb.append(cur.value);
            int leavesCount = 0;
            if (0 < cur.children.size()) {
                for (SuffixTreeNode child : cur.children) {
                    if (1 > child.children.size()) {
                        //child是叶子节点，叶子节点数+1
                        leavesCount += 1;
                    } else {
                        //child不是叶子节点，递归查找
                        leavesCount += dfsFindLongestSubstringOfLeastK(k, child, sb);
                    }
                }
            }
            if (k <= leavesCount) {
                //叶子节点数目达到阈值，更新候选答案
                if (maxLen < sb.length()) {
                    maxLen = sb.length();
                    candidate = sb.toString();
                }
            }
            //回溯
            sb.delete(delStart, delStart + cur.value.length());
            return leavesCount;
        }
    }

    static class SuffixTreeNode {
        String label;
        String value;
        List<SuffixTreeNode> children;

        public SuffixTreeNode(String label, String value) {
            this.label = label;
            this.value = value;
            this.children = new ArrayList<>();
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("SuffixTreeNode{");
            sb.append("label='").append(label).append('\'');
            sb.append(", value='").append(value).append('\'');
            sb.append('}');
            return sb.toString();
        }
    }
}
